package 剑指offer.双指针法;

/**
 * 依然是快慢指针法：
 * 既然有环的话，像一个田径场一样，快的总会会到慢的
 * <p>
 * 1. 设置快慢指针先确定是否有环
 * 2. 统计环中节点个数
 * 3. 快慢指针再从头出发找到入口
 */
public class 第23题链表中环的入口节点 {

    static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null)
            return null;
        if (pHead.next == pHead)
            return pHead;
        ListNode fast = pHead;
        ListNode slow = pHead;
        // 1. 找环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow)
                break;
        }
        // 2. 统计环里面的节点数
        int count = 1;
        ListNode meetPlace = fast;
        fast = fast.next;
        while (fast != meetPlace) {
            fast = fast.next;
            count++;
        }
        slow = pHead;
        while (count != 0) {
            slow = slow.next;
            count--;
        }
        fast = meetPlace;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }



    public static void main(String[] args) {
        ListNode l1 = new ListNode(-2);
        ListNode l2 = new ListNode(-1);
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(2);
        ListNode l6 = new ListNode(3);
        ListNode l7 = new ListNode(4);
        ListNode l8 = new ListNode(5);
        ListNode l9 = new ListNode(6);

        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = l7;
        l7.next = l8;
        l8.next = l9;
        l9.next = l6;

        ListNode ans = EntryNodeOfLoop(l1);
        System.out.println(ans.val);
    }
}
